using System;
using System.Collections;

namespace Graph
{	
	/// <summary>
	/// Implements IBasicGraph using adjacency lists.
	/// </summary>
	public class BasicGraph: IBasicGraph
	{
		private IList _vertices;

		public BasicGraph() 
		{
			_vertices = new ArrayList();
		}

		public bool IsEmpty()
		{
			return _vertices.Count==0;
		}
		public void AddVertex(Vertex v) 
		{
			_vertices.Add(v);
		}

		public void AddEdge(Vertex from, Vertex to) 
		{	//PRE (to,from) is not contained in the graph

			from.AddEdge(to);
		}
		public int GetNoOfVertices() 
		{
			return _vertices.Count;
		}

		public int GetNoOfEdges() 
		{
			int result = 0;
			foreach(Vertex v in _vertices)
			{
				result= result+v.OutDegree();
			}
			return result;
		}

		public bool ContainsEdge(Vertex from, Vertex to)
		{
			bool found = false;
			IEnumerator i = Edges();
			while (i.MoveNext() && !found)
			{
				Edge edge = (Edge)i.Current;
				//Console.WriteLine("Leder efter: '" + edge.From.Link.Url + "', faldt: '" + from.Link.Url + "'");
				if (edge.From.Link.Url.Equals(from.Link.Url) && edge.To.Link.Url.Equals(to.Link.Url))
					found = true;
			}
			return found;
		}

		public bool ContainsVertex(Vertex v)
		{
			bool found= false;
			IEnumerator i= Vertices();
			while(i.MoveNext() && !found)
			{
				Vertex w = (Vertex)i.Current;
				if(w.Link.Url.Equals(v.Link.Url))
					found=true;
			}
			return found;
		}

		public bool IsAdjacent(Vertex from, Vertex to) 
		{
			return (FindEdge(from, to) != null);
		}

		public void Clear() 
		{
			_vertices = new ArrayList();
		}

		public void RemoveEdge(Vertex from, Vertex to) 
		{
			Edge e = FindEdge(from, to);
			if (e!= null)
				e.From.RemoveEdge(e);
		}

		public void RemoveVertex(Vertex v) 
		{	//PRE	none

			_vertices.Remove(v);
			// but we also have to remove all the edges, where v is the to-vertex
			IEnumerator it = Vertices();
			while(it.MoveNext()) 
			{
				Vertex currVertex= (Vertex) it.Current;
				IList edges = (IList)currVertex.Edges();
				int i= 0;
				while (i<edges.Count) 
				{
					Edge e = (Edge) edges[i];
					if (e.To.Equals(v))
						edges.Remove(e);
					else
						i++;
				}
			}
		}

		public IEnumerator Vertices() 
		{
			return _vertices.GetEnumerator();
		}

		public IEnumerator Edges() 
		{	//PRE	none

			IList allEdges = new ArrayList();
			foreach(Vertex v in _vertices)
			{
				IEnumerator edges = v.Edges().GetEnumerator();
				while (edges.MoveNext())
					allEdges.Add(edges.Current);
			}
			return allEdges.GetEnumerator();
		}

		public IList GetAdjacencies(Vertex v)
		{
			Vertex w= (Vertex) _vertices[_vertices.IndexOf(v)];
			IList temp= (IList)w.Edges();
			IList returnList= new ArrayList();
			foreach(Edge e in temp)
				returnList.Add(e.To);
			return returnList;
		}

		public IList DepthFirstSearch(Vertex v)//for short: dfs
		{	//PRE The graph is connected and v is contained in the graph
			UnMark();//Make sure that all vertices are marked unvisited
			IList returnList= new ArrayList();
			Stack s= new Stack();
			v.Mark= true;
			returnList.Add(v);
			s.Push(v);

			while(s.Count!=0)
			{
				Vertex w= (Vertex)s.Peek();
				IList adjList= this.GetAdjacencies(w);
				Vertex u= GetNextUnMarked(adjList);
				if(u!=null)//There are unvisited neighbourgs
				{
					u.Mark= true;
					returnList.Add(u);
					s.Push(u);
				}
				else
					s.Pop();
			}

			return returnList;
		}

		private void UnMark()
		{
			for(int i= 0; i<_vertices.Count; i++)
				((Vertex)_vertices[i]).Mark= false;
		}

		private Vertex GetNextUnMarked(IList l)
		{	//POST	null is returned if there are no unmarked vertices in l

			bool found= false;
			int i= 0;
			Vertex v= null;
			while(!found && i<l.Count)
			{
				v= (Vertex)l[i];
				if(!v.Mark)
					found= true;
				else
					i++;
			}
			if(found)
				return v;
			else
				return null;
		}

		private Edge FindEdge(Vertex from, Vertex to) 
		{	//POST	returns null if there is no edge(from,to)

			Edge curr= null;;
			bool found= false;
			IEnumerator i= from.Edges().GetEnumerator();
			while (!found && i.MoveNext()) 
			{
				curr = (Edge) i.Current;
				if (curr.To.Equals(to))
					found=true;
			}
			if(found)
				return curr;
			else
				return null;
		}

	}
}
